package sliding_window

import "happy-go/leetcode/kit"

/*
1297.
给你一个字符串s ，请你返回满足以下条件且【出现次数最大】的【任意】子串的出现次数：

1.子串中不同字母的数目必须小于等于 maxLetters 。
2.子串的长度必须大于等于minSize 且小于等于maxSize 。

示例 1：
输入：s = "aababcaab", maxLetters = 2, minSize = 3, maxSize = 4
输出：2
解释：子串 "aab" 在原字符串中出现了 2 次。
它满足所有的要求：2 个不同的字母，长度为 3 （在 minSize 和 maxSize 范围内）。

示例 2：
输入：s = "aaaa", maxLetters = 1, minSize = 3, maxSize = 3
输出：2
解释：子串 "aaa" 在原字符串中出现了 2 次，且它们有重叠部分。

示例 3：
输入：s = "aabcabcab", maxLetters = 2, minSize = 2, maxSize = 3
输出：3

示例 4：
输入：s = "abcde", maxLetters = 2, minSize = 3, maxSize = 3
输出：0

提示：
1 <= s.length <= 10^5
1 <= maxLetters <= 26
1 <= minSize <= maxSize <= min(26, s.length)
s只包含小写英文字母。

*/

//滑动窗口
func maxFreqSW(s string, maxLetters int, minSize int, maxSize int) int {
	occurrences := make(map[string]int) //存储每个子串出现的次数
	countLetters := make([]int, 26)     //窗口内每个字母计数
	countUnique, left, right := 0, 0, 0 //窗口内唯一字母计数总数，左右指针

	//expand window
	for right < len(s) {
		idx := s[right] - 'a'
		countLetters[idx]++
		right++

		if countLetters[idx] == 1 { //如果是新字符
			countUnique++
		}

		//shrink window
		for right-left >= minSize && right-left <= maxSize {
			if countUnique <= maxLetters { //不同字母的数目必须小于等于 maxLetters
				subs := s[left:right] //截取子串
				occurrences[subs]++   //增加子串出现次数
			}

			d := s[left] - 'a'
			countLetters[d]--
			left++

			if countLetters[d] == 0 {
				countUnique--
			}

		}

	}

	m := 0
	for _, v := range occurrences {
		m = max(m, v)
	}
	return m
}

/*
求出现次数最大的，如果一个长串满足条件，那么子串也一定满足条件。也就是说，子串出现的次数一定大于长串出现的次数。
只需要看最短的子串即可。
然后按照数据范围可知不需要滑动窗口来优化，复杂度O(len(s)*minSize)
*/
func maxFreq(s string, maxLetters int, minSize int, maxSize int) int {
	occurrences := make(map[string]int) //存储每个子串出现的次数
	n := len(s)
	for i := 0; i < n-minSize+1; i++ {
		subs := s[i : i+minSize] //
		if kit.MaxTypeNumber(subs) <= maxLetters {
			occurrences[subs]++ //增加子串出现次数
		}
	}

	m := 0
	for _, v := range occurrences {
		m = max(m, v)
	}
	return m
}

/*
class Solution:
    def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
        n=len(s)
        d=collections.defaultdict(int)
        for i in range(n-minSize+1):
            temp=s[i:i+minSize]
            c=set(temp)
            if len(c)<=maxLetters:
                d[temp]+=1
        return max(d.values()) if d else 0

*/
